package 二叉树;

public class No938二叉搜索树的范围和 {

    /**
     * 给定二叉搜索树的根结点 root，返回值位于范围 [low, high] 之间的所有结点的值的和。
     *
     * 示例 1：
     * 输入：root = [10,5,15,3,7,null,18], low = 7, high = 15
     * 输出：32
     * 示例 2：
     * 输入：root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
     * 输出：23
     *  
     * 提示：
     * 树中节点数目在范围 [1, 2 * 104] 内
     * 1 <= Node.val <= 105
     * 1 <= low <= high <= 105
     * 所有 Node.val 互不相同
     */

    public int rangeSumBST(TreeNode root, int low, int high) {
        return dfs(root,low,high);
    }

    private int dfs(TreeNode node,int low,int high) {
        if(node==null){
            return 0;
        }
        int num=0;
        if(node.val>=low&&node.val<=high){
            num=node.val;
        }
        num+=dfs(node.left,low,high);
        num+=dfs(node.right,low,high);
        return num;
    }

    public static void main(String[] args) {
        TreeNode treeNode = TreeNode.getNodeByArr(new Integer[]{10, 5, 15, 3, 7, null, 18});
        No938二叉搜索树的范围和 n=new No938二叉搜索树的范围和();
        int result = n.rangeSumBST(treeNode, 7, 15);
        System.out.println(result);
    }

}
